Object-oriented computer programming languages such as JAVA and C# typically employ type hierarchies (concept ‘type’ and ‘class’ can be used interchangeably in this document). In computer languages, types are used to describe a given entity. For example, a computer language may employ a data structure having various fields used to describe the subject type. The information contained within the fields uniquely defines the type. Normally, types have hierarchy, i.e., one type can be a subtype or supertype of another, e.g., type “apple” is a subtype of type “fruit”, and is a supertype of type “red apple”. Once the type is determined for some data in computer memory, it may be necessary to determine whether that type is a subtype of another type. The type hierarchy may be viewed as a type tree having a root type base with subtypes of the root type, and subtypes of the subtype, etc. At run time, these languages determine if one type is a subtype of another. Type checking is a very common operation in object-oriented languages. This checking is accomplished through use of instructions at runtime, e.g., in virtual machines.
FIG. 1 illustrates a type checking process in accordance with the prior art. The system 100, shown in FIG. 1, includes data structures 105 through 109. Typically, data structures, that are stored in computer memory, contain among other data, a type field and a pointer to a supertype field. To determine the type of data structure 105, the type field 105A is checked and data structure 105 is determined to be of type E. It may also be necessary to determine if type E is a subtype of another type, for example it may be necessary to determine if type E is a subtype of type B. This is accomplished by checking the supertype pointer field 105b of data structure 105. Supertype pointer field 105b provides a pointer to the supertype of type E. The pointer is dereferenced to obtain type E's supertype (i.e. type D located at typefield 106a of data structure 106). Likewise, the supertype of type D is determined by obtaining a pointer to D's supertype and dereferencing the pointer. The process is continued until it is determined that type B is supertype of type E (or conversely that type E is a subtype of type B). In general, this process is done recursively until it is determined that a given type (e.g., type E) is a subtype of another type (e.g., type B) or until a root type is reached. In system 100, type A is a root type, that is type A is not a subtype of any other type. This is indicated by the fact that supertype pointer field 109B is null.
In system 100, each time a supertype pointer is obtained and dereferenced the process requires memory access. Such recursive memory access taxes processing resources and is time consuming.